import java.util.Stack;

public class LargestRectangleArea {
    // leetcode 柱状图中最大的矩形
    // https://leetcode.cn/problems/largest-rectangle-in-histogram/description/?envType=study-plan-v2&envId=top-100-liked
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        // 数组扩容，在头和尾各加入一个元素
        int [] newHeights = new int[heights.length + 2];
        newHeights[0] = 0;
        newHeights[newHeights.length - 1] = 0;
        for (int index = 0; index < heights.length; index++){
            newHeights[index + 1] = heights[index];
        }

        heights = newHeights;
        stack.add(0);
        int result = 0;
        for (int i = 1; i < heights.length; i++) {
            if (heights[i] > heights[stack.peek()]) {
                stack.add(i);
            }else if (heights[i] == heights[stack.peek()]) {
                stack.pop();
                stack.add(i);
            }else {
                while (heights[i] < heights[stack.peek()]) {
                    int mid = stack.pop();
                    int left = stack.peek();
                    int right = i;
                    int w = right - left - 1;
                    int h = heights[mid];
                    result = Math.max(result, w * h);
                }
                stack.add(i);
            }
        }
        return result;
    }

    public static void main(String[] args) {
        LargestRectangleArea largestRectangleArea = new LargestRectangleArea();
        int[] heights = new int[]{2,1,5,6,2,3};
        System.out.println(largestRectangleArea.largestRectangleArea(heights));
    }
}
